package com.zhouhong.muke_leetcode;

/**
 * @ClassName: Algorithm-and-Data-Structure
 * @Description:
 * @Author: zhouhong
 * @Create: 2021-04-04 18:51
 **/

//给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

public class LeetCode0042 {
    // 整体思路：每个柱子上面所能容纳的水为：它左边的最高的柱子和右边最高的柱子两者的较小者再减去当前的柱子高度
    // 所以只需要遍历一遍数组，每次找到它左边和右边的最高的柱子，然后拿到较小者减去当前柱子长度，每次累加当前柱子的存储水量即可
    public int trap(int[] height) {
        // 定义一个总水量
        int result = 0;
        // 循环遍历数组
        for (int i = 1; i < height.length - 1; i++) {
            // 定义每个元素左右找到的最大柱子
            int leftMax = 0, rightMax = 0;
            // 在 0---i 中找最大的那个柱子
            for (int j = 0; j < i; j++) {
                leftMax = Math.max(leftMax, height[j]);
            }
            // 在i---height.length上找最大的柱子
            for (int k = i; k < height.length; k++) {
                rightMax = Math.max(rightMax, height[k]);
            }
            // 总容水量累加
            result += Math.min(leftMax, rightMax) - height[i];
        }
        return result;
    }

}
